class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        for(int i=0; i<nums.length; ++i){
            for(int j=0; j<i; ++j){
                if(nums[i] > nums[j])
                dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }
        int res = 0;
        for(int i=0; i<nums.length; ++i){
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
/**
 * 经典问题，最长增长**子序列**
 * *注意！* 子序列和子串不是一个概念
 * 子序列可以不连续，子串必须连续
————————————————————————————————————
 *另外，我发现，动态规划问题，好像也没有这么难（线性）
 *但是开头的思路很难想到，所谓的举一反三，不是说，给你讲了知识点，就会做变形题，
 *而是说，做了一道例题，对它的变形也会做了，
 *例题都没做，就直接说，动态规划——就是一类拥有最优子结构的问题，好了，你现在去做吧
 *这总归不太合适不是
 */
 /*******************************
 * 二分查找的方法我还没有自己做出来*
 ********************************/
 public int lengthOfLIS(int[] nums) {
    int[] top = new int[nums.length];
    // 牌堆数初始化为 0
    int piles = 0;
    for (int i = 0; i < nums.length; i++) {
        // 要处理的扑克牌
        int poker = nums[i];

        /***** 搜索左侧边界的二分查找 *****/
        int left = 0, right = piles;
        while (left < right) {
            int mid = (left + right) / 2;
            if (top[mid] > poker) {
                right = mid;
            } else if (top[mid] < poker) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        /*********************************/
        
        // 没找到合适的牌堆，新建一堆
        if (left == piles) piles++;
        // 把这张牌放到牌堆顶
        top[left] = poker;
    }
    // 牌堆数就是 LIS 长度
    return piles;
}
